# -*- coding: utf-8 -*-
# @Time    : 2020/11/8 12:52
# @Author  : DuJiabao
# @File    : recusion.py
# @Description : this is a program tesing the efficiency of two ways of recusion.
from time import time


def fib1(N):
    """
    递归方法1
    :param N: 输入的N值
    :return: 输出值
    """
    if N <= 1:
        return 1
    return fib1(N - 1) + fib1(N - 2)


def fib2(N):
    """
    递归方法2
    :param N: 输入的N值
    :return: 输出值
    """
    dic = {}

    def recusion(N):
        if N <= 1:
            return 1
        if (N - 1) not in dic:
            dic[N - 1] = recusion(N - 1)
        if (N - 2) not in dic:
            dic[N - 2] = recusion(N - 2)
        return dic[N - 1] + dic[N - 2]

    return recusion(N)


if __name__ == '__main__':
    t = time()
    print(fib1(30))
    print(time() - t)

    t = time()
    print(fib2(30))
    print(time() - t)
